package array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * https://leetcode.cn/problems/merge-intervals/ 合并区间
 */
public class MergeSolution {
    public static void main(String[] args) {
        List<String> ans = Arrays.asList("a", "b", "c");
        String[] array = ans.toArray(new String[0]);
        for (String abc : array) {
            System.out.println(abc);
        }
    }

    /**
     * 合并区间。如果出现多次循环，很明显是一种错误解法
     * 先根据start排序的话就可以把模型变为
     * ------
     * ------
     * -------
     * 因为新加入的数据 start总是大于等于 上一条数据的start。所以只需要比较 当前数据的start 和上一条数据的end
     *
     * @param intervals intervals = [[1,3],[2,6],[8,10],[15,18]]
     * @return [[1, 6], [8, 10], [15, 18]]
     */
    public static int[][] merge(int[][] intervals) {
        // 根据第一列升序排序
        Arrays.sort(intervals, Comparator.comparingInt((int[] a) -> a[0]));
        // 如果用二维数组接受的话，不知道初始容量就会报错，所以这里使用List作为容器
        List<int[]> ans = new ArrayList<>();

        for (int i = 0; i < intervals.length; i++) {
            // ans 为空则直接添加
            if (ans.isEmpty()) {
                ans.add(intervals[i]);
            } else {
                int lastTo = ans.get(ans.size() - 1)[1];
                int from = intervals[i][0], to = intervals[i][1];
                if (lastTo >= from) // 相交则更新 ans 中的 lastTo
                    ans.get(ans.size() - 1)[1] = Math.max(lastTo, to);
                else { // 不相交则添在尾部
                    ans.add(intervals[i]);
                }
            }
        }
        // to array 转数组方法
        return ans.toArray(new int[ans.size()][]);
    }
}
